\section{Diskreter Logarithmus}
\subsection{Das DL-Problem}\label{dl-problem}
G ist eine endlich zyklische Gruppe der Ordnung n \newline
$\gamma$
ist ein Erzeuger dieser Gruppe \newline
1 ist das neutrale Element der Gruppe \newline
Die Gruppenordnung n ist bekannt \newline
Es wird eine obere Schranke für viele Algorithmen des DL-Problems benötigt. \newline
$\alpha$ ist ein Gruppenelement \newline
Ziel: Die kleinste nicht negative Zahl x finden für die  \newline
$\alpha = \gamma^{x} $ \newline
gilt. \newline
d.h. wir wollen den diskreten Logarithmus von $\alpha$ zur Basis $\gamma$ berechnen. \newline
Bedingung: Es muss entschieden werden ob es überhaupt einen
diskreten Log für dieses Beispiel gibt.
In der Kryptographie ist das aber irrelevant,
da es fast immer klar ist, dass ein solcher Log existiert.



\subsection{Enumeration}\label{enumeration}
Die einfachste Methode einen diskreten Log zu berechnen. Es werden für x = 1, 2, 3, 4, ... eingesetzt.
Sobald das Ergebnis positiv ist, ist der diskrete Log gefunden. \newline
Beispiel: \newline
Wir bestimmen den diskreten Logarithmus von 3 zur Basis 5 in $(\mathds{Z}/2017 \mathds{Z}) $ \newline
Probieren ergibt x = 1030.  \newline
Dafür werden 1029 Multiplikationen mod 2017 benötigt. \newline
Beispiel: \newline
$x = 0;$\newline
$\alpha=3;$\newline
$\gamma=5;$\newline
1. Schritt \newline
prüfen ob: 3 = $5^{0}$ mod 2017 \newline
2. Schritt
x wird um 1 erhöht. \newline
3 = $5^{1}$ mod 2017 \newline
Für die Berechnung der weiteren Schritte wird das Ergebnis von $5^{x}$ mod 2017 zwischengespeichert und für jeden weiteren Schritt mit $\gamma$ multiplizert. Dadurch wird der Aufwand beim Potenzieren reduziert, da nurnoch 1 Multiplikation durchgeführt werden muss.
\newline
Kryptische Verfahren arbeiten mit einem $x \geq 2^{160}$. In diesen Fällen ist das Eunumerationsverfahren nicht mehr anwendbar, da mindestens $2^{160 - 1}$ (im Durchschnitt $\left|G\right| / 2 $ Gruppenoperationen benötigt werden.
Anforderungen:
Speicherplatz für 3 Gruppenelement $(\alpha, \gamma, \gamma^{x})$ \newline
x-1 Multiplikationen

\subsection{Shanks Babystep Giantstep Algorithmus}\label{shanks}
Vorteil gegenüber Eunumeration: Weniger Gruppenoperationen
Nachteil: Es wird mehr Speicherplatz benötigt.
Man setzt:
$m = \left\lceil \sqrt{n}\right\rceil$ \newline
anschließend
$x = qm + r, 0 \leq r \leq m$ 
r = der Rest der Division von x durch m
q = Quotient der Division von x durch m
$\gamma^{qm+r} = \gamma^{x} = \alpha$
$\gamma^{qm+r} = \gamma^{x} = \alpha$
(Anm.: Exponenten trennen und Multiplikation mit $\gamma^{-r}$  )
$(\gamma^{m})^{q} = \alpha\gamma^{-r}.$ \newline
Die Menge der Babysteps wird folgendermaßen berechnet: \newline
$\textbf{B} = {( \alpha\gamma^{-r} , r) : 0 \leq r < m}.$ \newline
Wird ein Paar mit (1,r) gefunden so kann x=r gesetzt werden und man hat das DL-Problem gelöst.
Wird kein solches Paar gefunden bestimmt man \newline
$\delta = \gamma^{m} $ 
und prüft ob es ein Paar mit $(\delta^{q},r) zu \textbf{B}$ gehört. \newline
Wenn dies der Fall gilt: \newline
$\alpha\gamma^{-r} = \delta^{q} = \gamma^{qm}$
und man hat den diskreten Logarithmus 
$x = qm +r $
gefunden.
Für die effiziente Überprüfung, ob $\delta^{q}$ als erste Komponente eines Elementes der Babystep-Menge vorkommt, wird eine Hashtabelle mit der ersten Komponente jedes Elements als Schlüssel. 
\subsubsection{Beispiel 11.3.1.}\label{bsp}
Wir bestimmen den diskreten Logarithmus von 3 zur Basis
5 in $(\mathds{Z}/2017\mathds{Z})^{*}$. Es ist $\gamma = 5 + 2017\mathds{Z}$, $\alpha = 3+2017\mathds{Z})$,$ m = \left\lceil \sqrt{2016}\right\rceil= 45$.
Die Babystep-Menge ist \newline
\textbf{B} = {(3, 0), (404, 1), (1291, 2), ... ,  (1345, 44)}\newline
1. Element: $\alpha\gamma^{-r}$  = 3*$5^{0}$ = 3 mod 2017\newline
2. Element: $\alpha\gamma^{-r}$ = 3* $5^{-1}$ = 3 * $5^{-1}$ mod 2017\newline
Hierfür müssen wir nun die Inverse zu $5^(-1)$ berechnen mittels dem erweiterten Euklid oder durch ausprobieren. \newline In diesem Fall ist das Inverse Element 807.\newline
3*807 mod 2017 = 404
Die n\"achsten Schritte berechnet man, indem man das Ergebnis aus dem vorherigen Schnitt mit $5^{-1}$ multipliziert $($also 807 mod 2017, da mit der inversen von$ 5^{-1}$gerechnet wird$)$ \newline
Dies wiederholt man bis man die Grenze m (in diesem Beispiel 45) erreicht hat. \newline
Anschließend werden die Giantsteps berechnet mittels \newline
$\delta =\gamma^{m}  = 45 + 2017\mathds{Z}$  \newline
Die Giantsteps berechnen sich zu:\newline
45, 8, 360, 64, 863, 512, 853, 62, 773, 496, 133, 1951,
1064, 1489, 444, 1827, 1535, 497, 178, 1959, 1424, 1553.\newline
Rechenschritt:
1. Element: 451 mod 2017 = 45 mod 2017 = 45
2. Element: 452 mod 2017 = 2025 mod 2017 = 8
usw.\newline
Die n\"achsten Schritte k\"onnen, analog zum Babystep, über die Multiplikation des Ergebnisses aus dem vorhergegangenen Schritt mit 45 mod 2017 berechnet werden. \newline
Ergebnis:\newline
Man findet das Element (1553, 40) in der Babystep-Menge.\newline
Es ist also $???40 = 1553+2017\mathds{Z}$. \newline Andererseits wurde 1553 als 22. Giantstep gefunden. \newline
Also gilt\newline
$ \delta^{22} = \gamma^{22*45} = \alpha\gamma^{-40}.$\newline
Damit ist\newline
$\gamma^{22*45+40} = \alpha.$\newline
Als Lösung des DL-Problems findet man x = 22 * 45 + 40 = 1030. \newline Um die
Babystep-Menge zu berechnen, brauchte man 45 Multiplikationen. 22 weitere Multiplikationen werden zur Berechnung von $\delta$ also der Menge der Giantsteps benötigt. Die Anzahl an Multiplikationen ist deutlich geringer als beim Eunumerationsverfahren, jedoch ist der Speicherdarf deutlich höher, aufgrund der vielen zu speichernden Elemente. Zusätzlich ist es notwendig zu prüfen ob ein Element der Giantstep-Menge mit einem Element der Babystep-Menge übereinstimmt.\newline
\newline
Unter der Bedinung, dass Hashtabellen verwendet werden:\newline
Theorem 11.3.2. Der Babystep-Giantstep-Algorithmus benötigt $O(|G|)$
Multiplikationen und Vergleiche in G. Er muss $O(|G|)$ viele Elemente in G speichern.
Der Zeit- und Platzbedarf des Babystep-Giantstep-Algorithmus ist von der Größenordnung
$(|G|)$. Ist $|G| >$ $2^{160}$, so ist der Algorithmus in der Praxis nicht mehr einsetzbar.


\subsection{Der Pollard-$\rho$-Algorithmus}

Beim Pollard-$\rho$-Algorithmus bildet man eine eine unendliche Folge $(\beta_i)_i$
mit Elementen in einer endlichen Menge, wobei $\beta_i = f(\beta_{i-1})$ gebildet
wird. Diese unendlich Folge ist zyklisch und kann eine Vorperiode haben. Da die Menge
der Ergebnisse endlich ist erhalten wir zwangsläufig ein $f(\beta_i) = f(\beta_k)$.
Weil $f(\beta_i)$ aus $f(\beta_{i-1})$ gebildet wird muss $f(\beta_{i+1}) = f(\beta_{k+1})$
sein. Wenn man die Ergebnisse graphisch darstellt sehen sie aus, wie der Buchstabe $\rho$:
\begin{figure}[h]
\centering
\includegraphics[width=8cm]{ex5_diskreter_log/Pollard_Rho.png}
\caption{Graphische Darstellung der Ergebnisse}
\end{figure} 
 
Der Algorithmus benötigt gleichviele Gruppenoperationen, wie der Babystep-Giantstep-Algorithmus. 
Allerdings wird nur konstant viel Speicherplatz benötigt.

Um $f(\beta)$ zu definieren benötigen wir
drei paarweise disjunkte Mengen. Diese müssen bei Vereinigung wieder die Gesamtmenge bilden.

Wir definieren:
\begin{equation}\label{eq:pollardf}
f(\beta) = \left\{\begin{array}{ll} 
         \gamma \beta &\mbox{ falls } \beta\in G_1 \\
         \beta^2 & \mbox{ falls } \beta\in G_2 \\
         \alpha \beta &\mbox{ falls } \beta\in G_3
         \end{array} \right.
\end{equation} 

Außerdem wählen wir eine zufällige Zahl $x_0$ aus der Menge $\{1,\ldots,n\}$. Außerdem setzen wir
$\beta_0=\gamma^{x_0}$. Die Folge $\beta_i$ wird dann folgendermaßen berechnet:
\begin{equation}\label{eq:betaiplus1}
\beta_{i+1} = f(\beta_i)
\end{equation}

Diese Folge kann man dann auch so darstellen:
\begin{equation}\label{eq:betai}
\beta_i = \gamma^{x_i}\alpha^{y_i} \mbox{ mit } i\geq0 \mbox{ und } y_0 = 0 
\end{equation}

Für die folgenden $x_i$ und $y_i$ gilt:
\begin{equation}\label{eq:pollardx}
x_{i+1} = \left\{\begin{array}{ll} 
        x_i + 1 \mbox{ mod } n & \mbox{ falls } \beta_i\in G_1 \\
        2x_i \mbox{ mod } n &\mbox{ falls } \beta_i\in G_2 \\
        x_i & \mbox{ falls } \beta_i\in G_3
         \end{array} \right.
\end{equation}
\begin{equation}\label{eq:pollardy}
y_{i+1} = \left\{\begin{array}{ll} 
        y_i & \mbox{ falls } \beta_i\in G_1 \\
        2y_i \mbox{ mod } n &\mbox{ falls } \beta_i\in G_2 \\
        y_i + 1 \mbox{ mod } n & \mbox{ falls } \beta_i\in G_3
         \end{array} \right.
\end{equation}  

Da die Gruppe endlich viele Elemente besitzt muss es in dieser Folge zwei gleiche Gruppenelemente geben.
Es gibt also ein $i\geq0$ und ein $k\geq1$ mit denen gilt:
$$\beta_{i+k} = \beta_i$$
Daraus und aus (\ref{eq:betai}) folgt:
$$ \beta_i = \gamma^{x_i} \alpha^{y_i} = \gamma^{x_{i+k}} \alpha^{y_{i+k}} = \beta_{i+1} $$
Durch Umformen erhalten wir:
$$\gamma^{x_i-x_{i+k}} = \alpha^{y_{i+k}-y_i}$$
da $\alpha = \gamma^x$
$$\gamma^{x_i-x_{i+k}} = \gamma^{x(y_{i+k}-y_i)}$$
Deshalb gilt für den diskreten Logarithmus $x$ von $a$ zur Basis $\gamma$:
\begin{equation}\label{eq:discreteLog}
  (x_i-x_{i+k}) \equiv x(y_{i+k} - y_i) \mbox{ mod } n
\end{equation}

Diese Kongruenz muss nun gelöst werden. Falls die Lösung nicht eindeutig und auch nicht durch probieren
ermittelt werden kann fängt man mit einer anderen Zufallszahl $x_o$ von vorne an.

Durch das Geburtstagsparadox kann man bestimmen, dass $O(\sqrt{\left|G\right|})$ Folgenelemente berechnet
werden müssen, um mit einer Wahrscheinlichkeit von $>50\%$ zwei gleiche Folgenelemente zu erhalten. Wenn
man nun alle Tripel aus $(\beta_i, x_i, y_i)$ speichern muss benötigt man genausoviel Speicher, wie
beim Algorithmus von Shank. Die Werte $x_i$ und $y_i$ benötigen wir um das DL-Problem zu lösen.

Wir können den Algorithmus allerdings so verändern, dass er sehr viel weniger
Speicherplatz benötigt:
\begin{itemize}
  \item Wir speichern zu Beginn $(\beta_1, x_1, y_1)$.
  \item Immer wenn wir ein $(\beta_i, x_i, y_i)$ gespeichert haben berechnen wir $(\beta_j, x_j, y_j)$
  mit $j = i+1, i+2, \ldots$
  \item Wenn wir bis $j = 2i$ keine gleichen Folgenelemente finden speichern wir $(\beta_j, x_j, y_j)$
\end{itemize}
Wir müssen bei diesem Algorithmus also nur ein Element speichern.

Jetzt muss noch bewiesen werden, dass der neue Algorithmus immer zwei gleiche Folgenelemente findet.
Wir wissen, dass die Folge eine Vorperiode haben kann und auf jeden Fall eine Periode hat. Wir nehmen
an, dass die Vorperiode die Länge $s$ und die Periode die Länge $k$ hat. Sobald wir ein $i \geq s$ haben
liegt unser gespeichertes Element in der Periode. Sobald auch $i \geq k$ ist müssen wir ein Match finden,
weil wir denn mindestens einmal die Periode durchlaufen.

Beispiel:\\
Wir möchten mit dem Pollard-$\rho$-Algorithmus die Kongruenz $5^k \equiv 3 \mbox{ mod } 2017$ lösen.

Zuerst bestimmen wir die Teilmengen:
$$G_1 = \{1,\ldots,672\}, G_2 = \{673,\ldots,1344\}, G_1 = \{1345,\ldots,2016\}$$
Als Startwert wählen wir:
$$x_0 = 1023$$
Damit ist:
$$\beta_0 = 986$$
Wir berechnen:\\
mit (\ref{eq:pollardf}): $\beta_1 = \beta^2 \mbox{ mod } 2017 = 986^2 \mbox{ mod } 2017 \equiv 2$\\
mit (\ref{eq:pollardx}): $x_1 = 2x_0 \mbox{ mod } 2016 = 2*1023 \mbox{ mod } 2016 \equiv 30$\\
mit (\ref{eq:pollardy}): $y_1 = 2y_0 \mbox{ mod } 2016  = 2*0 \mbox{ mod } 2016 \equiv 0$\\
usw.

Dadurch entsteht, wenn wir alle gespeicherten und das letzte Tripel angeben entsteht die 
Tabelle \ref{tab:tripel}.

\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|c|}
\hline$j$&$\beta_j$&$x_j$&$y_j$\\ \hline\hline
 0& 986&1023&   0\\
 1&   2&  30&   0\\
 2&  10&  31&   0\\
 4& 250&  33&   0\\
 8&1366& 136&   1\\
16&1490& 277&   8\\
32& 613& 447& 155\\
64&1476&1766&1000\\
98&1476& 966&1128\\\hline
\end{tabular}
\caption{Gespeicherte Tripel $(\beta_j x_j, y_j)$}
\label{tab:tripel}
\end{table}

Die Periodenlänge ist 32 und wir können $i$ und $k$ ablesen:
$$i = 64 \mbox{ und } j = 32$$

Daraus folgt:
$$5^{1766-966} \equiv 3^{1128-1000} \mbox{ mod } 2017$$
$$5^{800} \equiv 3^{128} \mbox{ mod } 2017$$

Um $x$ berechnen zu können müssen wir also die Kongruenz
$$128x \equiv 800 \mbox{ mod } 2016$$
lösen. Da $gcd(128,2016) = 32$ ein Teiler von 800 ist können wir schrieben:
$$4z \equiv 25 \mbox{ mod } 63$$
Wir können nun $z$ mit dem erweiterten Euklid berechnen und erhalten 
$$z \equiv 22 \mbox{ mod } 2017$$

Damit können wir auch die Kongruenz mit $x$ bestimmen.
Es ist:
$$x \equiv z \mbox{ mod }63$$
Das heißt für obige Kongruenz mit $x$ muss x einen folgender Werte haben:
$$x = 22 + k*63 \mbox{ für } 0 \leq k < 32$$
Durch ausprobieren findet man mit $k=16$ den diskreten Logarithmus $x=1030$

\subsection{Der Pohlig-Hellman-Algorithmus}
Mit dem Pohlig-Hellman-Algorithmus kann man das Problem der Berechnung des diskreten Logarithmus auf
Gruppen von Primzahlenordnungen reduzieren. Das geht aber nur dann, wenn man die Faktorisierung der
Gruppenordnung kennt. Damit ist die Ordnung der Gruppe kleiner, in der das DL-Problem gelöst werden muss.
Der Aufwand für die Berechnung wird damit auch kleiner.
Zur Erinnerung: Die Zerlegung in Primfaktoren ist so definiert:
$$n = \prod_{p|n}p^{e(p)}$$
Beispiel: Die Ordnung der primen Restklassengruppe mod 2017 ist:
$$2016 = 2^5*3^2*7$$

\subsubsection{Reduktion auf Primzahlpotenzordnung}
Statt in $({\mathbb Z}/2017{\mathbb Z})^*$ zu rechnen (mit Ordnung 2016), löst man verwandte Probleme in Untergruppen 
von $({\mathbb Z}/2017{\mathbb Z})^*$, wobei die Untergruppen die Ordnung $2^5$, $3^2$ und $7$ haben.

Für jeden Primteiler $p$ der Gruppenordnung $n$ setzen wir:
$$\begin{array}{lll}
  n_p = n/p^{e(p)} ,& \gamma_p = \gamma^{n_p} ,& \alpha_p = \alpha^{n_p}
\end{array}$$

$\gamma_p$ erzeugt eine Untergruppe mit $p^{e(p)}$ Elementen.\\
Beispiel: $\gamma = 3$, d.h. $\gamma_3 \equiv 3^{2^5*7} \equiv 1933 \mod 2017$ und die Menge der 
Potenzen von $\gamma_3$ umfasst 9 Elemente:
$$\{1, \underline{\mathbf{1933}}, 1005, 294, 1525, 988, 1722, 576, 24\}$$
$$\alpha_p \equiv 3^{2^5*7} \equiv \underline{\mathbf{1933}}$$

Außerdem gilt:
Die erzeugte zyklische Untergruppe $\gamma_p$ von G enthält $\alpha_p$. Deshalb existiert auch dieser
diskrete Logarithmus.

Jetzt müssen wir noch $x$ berechnen. Wir definieren für alle Primteiler $p$ von $n$ $x(p)$ als den
diskreten Logarithmus von $a_p$ zur Basis $\gamma_p$. $x$ ist dann die Lösung der simultanen Kongruenz
$x \equiv x(p)$ für alle Primzahlen $p$.
$x$ ist dann der diskrete Logarithmus von $\alpha$ zur Basis $\gamma$.

Wir können also $x$ berechnen, indem wir zuerst alle $x(p)$ bestimmen und dann den chinesischen Restsatz
anwenden. WIr können $x(p)$ mit dem Algorithmus von Shank oder Pollard berechnen und benötigen dafür
$O(\sqrt{p^{e(p)}})$ Operationen. Die Rechenzeit des chinesischen Restsatzes kann vernachlässigt werden.

\subsubsection{Reduktion auf Primzahlordnung}
Wir müssen das DL-Problem weiter vereinfachen. Wir reduzieren die DL-Berechnung in
einer zyklische Gruppe von Primzahlpotenzordnungen auf die Berechnung in einer
Gruppe von Primzahlordnungen.

Es ist also $\left|G\right| = n = p^e$. Wir suchen $x$ mit $\gamma^x = a$. Wir wissen , dass 
$x < p^e$. Deshalb kann die p-adische Darstellung verwendet werden:
$$x = x_0+x_1p+\ldots+x_{e-1}p^{e-1} \mbox{ mit } 0 \leq x_i < p \mbox{ und } 0 \leq i \leq e-1$$
Wenn wir die Gleichung $\gamma^x=\alpha$ mit $p^{e-1}$ potenzieren erhalten wir:
\begin{equation}\label{eq:primordnung}
\begin{split}
  \gamma^{p^{e-1}x} = \alpha^{p^{e-1}}\\
  = (\gamma^{x_0+x_1p+\ldots+x_{e-1}p^{e-1}})^{p^{e-1}}\\
  = \gamma^{x_0p^{e-1}+x_1p^e+x_2p^{e+1+\ldots+x_{e-1}p^{2(e-1)}}}\\
  = \gamma^{x_0p^{e-1}}*\gamma^{x_1p^e}*\ldots*\gamma^{x_{e-1}p^{2(e-1)}}
\end{split}
\end{equation}
Wir können den kleinen Satz von Fermat anwenden:\\
Die Ordnung von $\gamma$ ist Teiler von $|G|$ also:
\begin{equation}
\begin{split}
  \gamma^{x_1p^e} = (\gamma^{p^e})^{x_1} = 1\\
  \gamma^{x_2p^{e+1}} = (\gamma^{p^e})^{x_2p} = 1
\end{split}
\end{equation}
usw.\\
Daraus folgt dann:
\begin{equation}\label{eq:primfermat}
  (\gamma^{p^{e-1}})^{x_0} = \alpha^{p^{e-1}}
\end{equation}
Damit ist $x_0$ die Lösung eines DL-Problems in einer Gruppe der Ordnung $p$, weil $\gamma^{p^{e-1}}$
die Ordnung $p$ hat. Die anderen Koeffizienten können rekursiv berechnet werden. Wir nehmen an, 
dass schon alle Koeffizienten bis $x_{i-1}$ bestimmt sind:
$$\gamma^{x_ip^i+\ldots+x_{e-1}p^{e-1}} = \alpha\gamma^{-(x_0+x_1p+\ldots+x_{i-1}p^{i-1})}$$
Wir bezeichnen das Gruppenelement auf der rechten Seite mit $a_i$ und potenzieren die Gleichung mit
$p^{e-i-1}$. Dann erhalten wir für die Berechnung der Koeffizienten folgende Gleichung:
\begin{equation}\label{eq:rekkoeff}
  (\gamma^{p^{e-1}})^{x_i} = \alpha_i^{p^{e-i-1}} \mbox{ für } 0 \leq i \leq e-1
\end{equation}
Um die Koeffizienten zu berechnen müssen also $e$ DL-Probleme in Gruppen der Ordnung $p$ gelöst
werden, um $x_i$ zu bestimmen.

\subsubsection{Beispiel}
$$5^x \equiv 3 \mbox{ mod } 2017$$

Das DL-Problem $5^x \equiv 3 \mod 2017$ wird in einer Untergruppe der Ordnung $2^5$ mittels
Reduktion auf Primzahlpotenzordnungen gelöst.

Die Gruppenordnung haben wir schon oben bestimmt:
$$n = 2016 = 2^5*3^2*7$$
Wir haben auch:
$$n_2 = 3^2*7$$
$$\gamma_2 = 5^{3^2*7}$$
$$\alpha_p = 3^{3^2*7}$$

Zuerst berechnen wir $x(2) = x \mbox{ mod } 2^5$:
ergibt sich die Kongruenz:
$$(5^{n_2})^{x(2)} \equiv 3^{n_2} \mbox{ mod } 2017$$
$$500^{x(2)} \equiv 913 \mbox{ mod } 2017$$

Das DL-Problem $500^x(2) \equiv 913 \mod 2017$ wird in einer Untergruppe der Ordnung $2$ mittels
Reduktion auf die Primzahlordnung gelöst.

Wir wissen:
$$
\begin{array}{llll}
  \gamma_2 = 500, & \alpha = 913, & p = 2, & e = 5 
\end{array}
$$

$$x(2) = x_0(2)+x_1(2)*2+x_2(2)*2^2+x_3(2)*2^3+x_4(2)*2^4$$
Mit (\ref{eq:primfermat}) berechnen wir $x_0(2)$:
$$500^{(2^4x_0(2))} \equiv 913^{2^4} \mbox{ mod } 2017$$
$$2016^{x_0(2)} \equiv 1 \mbox{ mod } 2017$$
Deshalb ist $x_0(2)=0$ und $a_0 = a_1 = 913$\\
Wir berechnen die weiteren Koeffizienten mit (\ref{eq:rekkoeff}):
$$2016^{x_1(2)} \equiv 913^{2^3} \mbox{ mod } 2017$$
$$2016^{x_1(2)} \equiv 2016 \mbox{ mod } 2017$$
$x_1(2)$ ist also 1. Wir berechnen $a_2$:
$$a_2 \equiv 913 * 500^{-(0 + 1*2)} \mbox{ mod } 2017 \equiv 1579$$
$$2016^{x_2(2)} \equiv 1579^{2^2} \mbox{ mod } 2017$$
$$2016^{x_2(2)} \equiv 2016 \mbox{ mod } 2017$$
Daraus folgt, dass auch $x_2(2) = 1$ ist. Wenn man diese Rechnung fortsetzt erhält man
$x_3(2) = x_4(2) = 0$\\
Mit diesen Werten kann man nun $x(2)$ berechnen:
$$x(2) = 0+1*2+1*2^2+0*2^3+0*2^4 = 6$$

$x(3)$ und $x(7)$ werden analog errechnet. Man erhält:
$$
\begin{array}{ll}
  x(3) = 4 & x(7) = 1
\end{array}
$$

Wir erhalten damit $x$ als Lösung einer simultanen Kongruenz, die wir mit dem chinesichen
Restsatz berechnen können.
$$
\begin{array}{lll}
 x \equiv 6 \mbox{ mod } 32, & x \equiv 4 \mbox{ mod } 9, & x \equiv 1 \mbox{ mod } 7 
\end{array}
$$
Die Lösung ist $x = 1030$
\subsubsection{Analyse des Algorithmus}
Die Zeit, die der Pohlig-Hellman-Algorithmus benötigt wird von Quadratwurzel des höchsten
Primteilers dominiert. Wenn also der größte Primteiler der Gruppenordnung zu klein ist,
kann man den diskreten Logarithmus in dieser Gruppe sehr einfach berechnen.

Beispiel: Die Zahl $p=2*3*5^{278} +1$ ist eine Primzahl mit der binären Länge 649. Da der
größte Primteiler der Gruppe 5 ist kann der diskrete Logarithmus in dieser Gruppe sehr 
einfach berechnet werden. Deshalb sollte diese Zahl auch nicht im ElGamal-Verfahren
benutzt werden.